package ljl.codetop300;

import commons.TreeNode;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * 要点：left 永远是 null，right 是下一个节点
 * 整个相当与先序遍历
 *
 * 既然整个先序遍历我直接先序遍历不就完了吗
 * 试了试，不行
 *
 * 算了不会做
 * 但是后来又蒙对了，我都不知道怎么回事
 *
 */
public class _114_flatten_tree_to_list {

  static class test {

    public void flatten(TreeNode root) {
      if (root == null) return;
      TreeNode p = root;
      TreeNode left = root.left;
      TreeNode right = root.right;

      flatten(root.left);
      if (left != null) {
        root.right = left;
        root.left = null;
        p = left;
        while (p.right != null) {
          p = p.right;
        }
      }
      flatten(right);
      p.right = right;
    }
  }

  /**
   * 这个做法最简单
   */
  static class off_1 {
    public void flatten(TreeNode root) {
      List<TreeNode> list = new ArrayList<>();
      preorderTraversal(root, list);
      int size = list.size();
      for (int i = 1; i < size; i++) {
        TreeNode prev = list.get(i - 1), curr = list.get(i);
        prev.left = null;
        prev.right = curr;
      }
    }

    public void preorderTraversal(TreeNode root, List<TreeNode> list) {
      if (root != null) {
        list.add(root);
        preorderTraversal(root.left, list);
        preorderTraversal(root.right, list);
      }
    }
  }

  /**
   * 和前一个做法一样，只会更慢不会更快
   */
  static class off_2 {
    public void flatten(TreeNode root) {
      List<TreeNode> list = new ArrayList<>();
      Deque<TreeNode> stack = new LinkedList<>();
      stack.push(root);
      while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        list.add(node);
        if (node.right != null) stack.push(node.right);
        if (node.left != null) stack.push(node.left);
      }
      int size = list.size();
      for (int i = 1; i < size; i++) {
        TreeNode prev = list.get(i - 1), curr = list.get(i);
        prev.left = null;
        prev.right = curr;
      }
    }
  }

  /**
   * 只是少了一趟遍历，效果和上面是一样的
   */
  static class off_3 {
    public void flatten(TreeNode root) {
      if (root == null) {
        return;
      }
      Deque<TreeNode> stack = new LinkedList<>();
      stack.push(root);
      TreeNode prev = null;
      while (!stack.isEmpty()) {
        TreeNode curr = stack.pop();
        if (prev != null) {
          prev.left = null;
          prev.right = curr;
        }
        TreeNode left = curr.left, right = curr.right;
        if (right != null) {
          stack.push(right);
        }
        if (left != null) {
          stack.push(left);
        }
        prev = curr;
      }
    }
  }

  /**
   * 这个题解非常巧妙，需要时间来消化
   */
  static class off_o1 {
    public void flatten(TreeNode root) {
      TreeNode curr = root;
      while (curr != null) {
        if (curr.left != null) {
          TreeNode next = curr.left;
          TreeNode predecessor = next;
          while (predecessor.right != null) {
            predecessor = predecessor.right;
          }
          predecessor.right = curr.right;
          curr.left = null;
          curr.right = next;
        }
        curr = curr.right;
      }
    }
  }

  static class copy_off_o1 {
    public void flatten(TreeNode root) {
      TreeNode p = root;
      while (p != null) {
        if (p.left != null) {
          TreeNode pred = p.left;
          while (pred.right != null) pred = pred.right;
          pred.right = p.right;
          p.right = p.left;
          p.left = null;
        }
        p = p.right;
      }
    }
  }

}
